package gaobo.priorityqueue;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class TestHeap {

    public int[] elem;

    public int usedSize;//有效的数据个数

    public static final int DEFAULT_SIZE = 10;

    public TestHeap(){
        elem = new int[DEFAULT_SIZE];
    }

    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }
    //大根堆 时间复杂度 O(n)
    public void createHeap(){
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            //统一的调整方案
            shiftDown(parent,usedSize);

        }
    }

    /**
     *向下调整
     * @param parent 每棵子树的根节点
     * @param len 每棵子树调整的结束位置 不能大于>len
     */
    private void shiftDown(int parent, int len){
        int child = 2*parent + 1;
        //1.必须保证有左孩子
        while (child < len){
            //child+1 < len && 保证有右孩子
            if (child+1 < len && elem[child] < elem[child+1]){
                child++;
            }
            if (elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    //大根堆的插入
    public void offer(int val){
        //扩容
        if (isFull()){
            Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[usedSize] = val;
        usedSize++;
        //让这棵树再次变成大根堆
    }
    //向上调整
    private void shiftUp(int child){
        int parent = (child-1) / 2;
        while (child>0) {
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

    private boolean isFull(){
        return usedSize == elem.length;
    }

    //堆的删除（一定是删堆顶元素，否则没意义）
    public int pop(){
        if (isEmpty()){
            return -1;
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;
        //保证它仍然是一个大根堆
        shiftDown(0,usedSize);
        return tmp;
    }
    private boolean isEmpty(){
        return usedSize == 0;
    }



    //面试题 力扣【17.14】 最小K个数

    /**
     * 时间复杂度：O(N+KlogN)
     * @param arr
     * @param k
     * @return
     */
    public static int[] smallestK2(int[] arr, int k){
        //1.建立一个小根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        //2.取出数组当中的每个元素，存放在小根堆当中
        for (int i = 0; i < arr.length; i++) {
            minHeap.offer(arr[i]);
        }
        //3.弹出k个元素，存放到数组当中，返回即可 Klogn
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();
        }
        return tmp;

    }

    public static void main(String[] args) {
        int[] array = {1,5,2,9,8,20,18};
        smallestK2(array,3);
    }

    /**
     * 区别:
     * 1.没有整体建堆。
     * 2.遍历剩下n-k个元素，每个元素和堆顶比较。
     * 时间复杂度 ~O(NlogK)
     */

    public static int[] smallestK3(int[] arr, int k){
        if (arr == null || k == 0){
            return null;
            //return new int[0]
        }

        //1.建立一个大根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

        //2.
        for (int i = 0; i < arr.length; i++) {
            if (minHeap.size() < k){
                minHeap.offer(arr[i]);
            }else {
                //当前数组的元素时arr[i]
                int val = minHeap.peek();
                if (val > arr[i]){
                    //弹出大的
                    minHeap.poll();
                    //放进小的
                    minHeap.offer(arr[i]);
                }else {

                }
            }
        }
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = minHeap.poll();
        }
        return tmp;
    }

}
